//<p>给定一个不含重复数字的数组 <code>nums</code> ，返回其 <em>所有可能的全排列</em> 。你可以 <strong>按任意顺序</strong> 返回答案。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [1,2,3]
//<strong>输出：</strong>[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [0,1]
//<strong>输出：</strong>[[0,1],[1,0]]
//</pre>
//
//<p><strong>示例 3：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [1]
//<strong>输出：</strong>[[1]]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>1 &lt;= nums.length &lt;= 6</code></li>
//	<li><code>-10 &lt;= nums[i] &lt;= 10</code></li>
//	<li><code>nums</code> 中的所有整数 <strong>互不相同</strong></li>
//</ul>
//<div><div>Related Topics</div><div><li>数组</li><li>回溯</li></div></div><br><div><li>👍 2003</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import cn.hutool.json.JSONUtil;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 全排列
 * @author DY Rising
 * @date 2022-05-11 20:28:24
 */
public class P46_Permutations{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P46_Permutations().new Solution();
        System.out.println(JSONUtil.toJsonStr(solution.permute(new int[] {1,2,3})));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> rtns = new ArrayList<>();
        dfs(nums, rtns, new ArrayDeque<>(), new HashMap<>(), 0);
        return rtns;
    }

    public void dfs(int[] nums, List<List<Integer>> rtns, Deque<Integer> path, Map<Integer, Integer> map, int depth) {
        //已经到树叶子端
        //System.out.println("路径：" + JSONUtil.toJsonStr(path) + ", 去重：" + JSONUtil.toJsonStr(map) + ", 深度：" + depth);
        if (depth == nums.length) {
            rtns.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            //已经存在跳过
            if (map.get(nums[i]) != null) continue;
            path.add(nums[i]);
            map.put(nums[i], nums[i]);
            dfs(nums, rtns, path, map, depth + 1);
            path.removeLast();
            map.remove(nums[i]);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
